<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>排序算法之基数排序</title>
</head>
<body>
  <script type="text/javascript">
    function radixSort(array, radixBase = 10) {
      if (array.length < 2) {
        return array;
      }
      const minValue = Math.min(...array);
      const maxValue = Math.max(...array);
      // 基数排序也用来排序整数，我们就从最后一位开始排序所有的数，这个算法也可以被修改成支持排序字母字符。
      let significantDigit = 1;
      // 首先只会基于最后一位有效位对数字进行排序，在下次迭代时，我们会基于第二个有效位进行排序(十位数字)，
      // 然后是第三个有效位(百位数字)，以此类推。我们继续这个过程直到没有待排序的有效位
      // 这也是为什么我们需要知道数组中的最小值和最大值。
      // 如果数组中包含的值都在 1~9，以下循环只会执行一次。如果值都小于 99，则循环会执行第二次，以此类推。
      while ((maxValue - minValue) / significantDigit >= 1) {
        array = countingSortForRadix(array, radixBase, significantDigit, minValue);
        significantDigit *= radixBase;
      }
      return array;
    }

    function countingSortForRadix(array, radixBase, significantDigit, minValue) {
      let bucketsIndex;
      const buckets = [];
      const res = [];
      // 基于基数初始化桶，由于我们排序的是十进制数，那么需要 10 个桶。
      for (let i = 0; i < radixBase; i++) {
        buckets[i] = 0;
      }
      // 基于数组中数的有效位进行计数排序
      for (let i = 0; i < array.length; i++) {
        bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase); // 有效位
        buckets[bucketsIndex]++; // 计数排序
      }
      // 由于我们进行的是计数排序，我们还需要计算累积结果来得到正确的计数值
      for (let i = 1; i < radixBase; i++) {
        buckets[i] += buckets[i - 1];
      }
      // 对原始数组中的每个值，我们会再次获取它的有效位并将它的值移动到 res 数组中(从 buckets 数组中减去它的计数值)
      for (let i = array.length - 1; i >= 0; i--) {
        bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase);
        res[--buckets[bucketsIndex]] = array[i];
      }
      return res;
    }

    const arr = [101, 66, 389, 43, 821, 132, 128];
    console.log(radixSort(arr));
  </script>
</body>
</html>